摘要 :
Reliability assessment is of significant importance in the design maintenance and improvement of multiprocessor or multicomputer systems. System-level diagnosis is a primary strategy to identify the faulty processors in a multipro...
展开
Reliability assessment is of significant importance in the design maintenance and improvement of multiprocessor or multicomputer systems. System-level diagnosis is a primary strategy to identify the faulty processors in a multiprocessor system through resolving the syndrome of testing. In this paper, we first establish the algebraic structure of n-dimensional DQcube DQ(m, d, n), and then show that the classic, strong, pessimistic and conditional diagnosability of DQ(m, d, n) are n + 1, n + 1, 2n, and 4n - 3, respectively. As by-products, the tightly super and 3-extra connectivity of DQcube are also established. (C) 2019 Elsevier B.V. All rights reserved.
收起
摘要 :
A system is t/t-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free processor mistaken as a faulty one. The pes...
展开
A system is t/t-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free processor mistaken as a faulty one. The pessimistic diagnosability of a system G, denoted by t(p)(G), is the maximal number of faulty processors so that the system G is t/t-diagnosable. The pessimistic diagnosability of alternating group graphs AG(n) (Tsai, 2015); BC networks (Fan, 2005; Tsai, 2013); the k-ary n-cube networks Q(n)(k), (Wang et al., 2012); regular graphs including the alternating group networks AN(n) (Hao et al., 2016) etc. But most of these results are about networks G with cn(G) = k + 2 and k >= 3, t(p)(S-n,S-k) = n + k - 3 for n >= k + 2 and k >= 3, and t(p)(BHn) = 2n for n >= 2. As corollaries, the pessimistic diagnosability of the known results about AG(n) and AN(n) is obtained directly. (C) 2016 Elsevier B.V. All rights reserved.
收起
摘要 :
The g-extra connectivity of a multiprocessor system modeled by a graph G, denoted by K_o~(g)(G), is the minimum number of removed vertices such that the network is disconnected and each residual component has no less than g + 1 ve...
展开
The g-extra connectivity of a multiprocessor system modeled by a graph G, denoted by K_o~(g)(G), is the minimum number of removed vertices such that the network is disconnected and each residual component has no less than g + 1 vertices. The t/k-diagnosis strategy can detect up to t faulty processors which might include at most k misdiagnosed processors. These two parameters are important to measure the fault tolerant ability of a multiprocessor system. The extra connectivity and t/k-diagnosability of many well-known networks have been investigated extensively and independently. However, the general relationship between the extra connectivity and the t/k-diagnosability of general regular networks has not been established. In this paper, we explore the relationship between the k-extra connectivity and t/k-diagnosability for regular networks under the classic PMC diagnostic model. More specifically, we derive the relationship between 1-extra connectivity and pessimistic diagnosability for regular networks. Furthermore, the t/k-diagnosability and pessimistic diagnosability of some networks, including star network, BC networks, Cayley graphs generated by transposition trees etc., are determined.
收起
摘要 :
The pessimistic diagnosis strategy is a classic strategy based on the PMC model. A system is t/t-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size ...
展开
The pessimistic diagnosis strategy is a classic strategy based on the PMC model. A system is t/t-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistaken as a faulty one. The pessimistic diagnosability of a system G, denoted by t(p)(G), is the maximal number of faulty processors so that the system G is t/t-diagnosable. In this paper, we study the pessimistic diagnosabilities of some general k-regular k-connected graphs G(n). The main result t(p)(G(n)) = 2k - 2 - g under some conditions is obtained, where g is the maximum number of common neighbors between any two adjacent vertices in Gn. As applications of the main result, every pessimistic diagnosability of many famous networks including some known results, such as the alternating group networks AN(n), the k-ary n-cubes Q(n)(k), the star graphs S-n, the matching composition networks G(G(1), G(2); M) and the alternating group graphs AG(n), are obtained. (C) 2015 Elsevier B.V. All rights reserved.
收起
摘要 :
The Bouwer graph B(k, m, n), proposed in 1970, is defined for every triple (k, m, n) of integers greater than 1 with 2~m ≡ 1 mod n. It has many good properties, such as vertex-transitive and edge-transitive. Conder and ?itnik use...
展开
The Bouwer graph B(k, m, n), proposed in 1970, is defined for every triple (k, m, n) of integers greater than 1 with 2~m ≡ 1 mod n. It has many good properties, such as vertex-transitive and edge-transitive. Conder and ?itnik use a cycle-counting argument to prove that almost all of the Bouwer graphs are half-arc-transitive in 2016. In this paper, by exploring the structure properties of B(k_(ìmìn)), we deduced that the pessimistic diagnosability under the PMC model is - 2, for k > 2, m > 6 and n> 7.
收起
摘要 :
Let Gamma(n) be the symmetric group on {1, 2, ..., n}, and S be the generating set of Gamma(n). The corresponding Cayley graph is denoted by Gamma(n)(S). If all elements of S are transpositions, a simple way to depict S is via a g...
展开
Let Gamma(n) be the symmetric group on {1, 2, ..., n}, and S be the generating set of Gamma(n). The corresponding Cayley graph is denoted by Gamma(n)(S). If all elements of S are transpositions, a simple way to depict S is via a graph, called the transposition generating graph of S, denoted by A(S) (or say simply A), where the vertex set of A is {1, 2, ..., n}, there is an edge in A between i and j if and only if the transposition (ij) is an element of S, and Gamma(n)(S) is called a Cayley graph obtained from a transposition generating graph A. In this paper, by exploring and utilizing the structural properties of these Cayley graphs, we obtain that the pessimistic diagnosability of Gamma(n)(S) is equal to 2 vertical bar E(A)vertical bar - 2 if A has no triangles or 2 vertical bar E(A)vertical bar - 3 if A has a triangle. As corollaries, the pessimistic diagnosability of many kinds of graphs such as Cayley graphs generated by unicyclic graphs, wheel graphs, complete graphs, and tree graphs is obtained. (C) 2018 Elsevier B.V. All rights reserved.
收起
摘要 :
A system is t/t-diagnosable if, provided the number of faulty processor is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistake as a faulty one. The pessimisti...
展开
A system is t/t-diagnosable if, provided the number of faulty processor is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistake as a faulty one. The pessimistic diagnosability of a system G, denoted by t_p(G), is the maximal number of faulty processors so that the system G is t/t-diagnosable. The augmented cube AQ_n, proposed by Choudum and Sunitha [Networks 40 (2) (2002) 71-84], has many attractive properties such as regularity, strong connectivity and symmetry. In this paper, we determine the pessimistic diagnosability of the n-dimensional augmented cube AQ_n and prove that t_p(AQ_n) = 4n - 8 for n ≥ 5.
收起
摘要 :
Extra connectivity and the pessimistic diagnosis are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processor. The pessimistic diagnosis strategy is a classic strategy based on the PMC m...
展开
Extra connectivity and the pessimistic diagnosis are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processor. The pessimistic diagnosis strategy is a classic strategy based on the PMC model in which isolates all faulty vertices within a set containing at most one fault-free vertex. In this paper, the result that the pessimistic diagnosability t(p) (G) equals the extra connectivity K-1 (G) of a regular graph G under some conditions are shown. Furthermore, the following new results are gotten: the pessimistic diagnosability t(p) (S-n(2)) = 4n - 9 for split-star networks S-n(2); t(p) (Gamma(n)) = 2n - 4 for Cayley graphs generated by transposition trees Gamma(n); t(p) (Gamma(n) (Delta)) = 4n - 11 for Cayley graph generated by the 2-tree Gamma n (Delta); t(p) (BPn) = 2n - 2 for the burnt pancake networks BPn. As corollaries, the known results about the extra connectivity and the pessimistic diagnosability of many famous networks including the alternating group graphs, the alternating group networks, BC networks, the k-ary n-cube networks etc. are obtained directly. (C) 2017 Published by Elsevier B.V.
收起
摘要 :
In a simple graph G= (V(G), E(6)), let n_0 be the minimum cardinality of the neighbourhoods of any two adjacent vertices, i.e. n_0 = min{|N_G({u, v})||(u, v) e E(G)}. Let κ(G) be the connectivity of G. In this paper, we prove tha...
展开
In a simple graph G= (V(G), E(6)), let n_0 be the minimum cardinality of the neighbourhoods of any two adjacent vertices, i.e. n_0 = min{|N_G({u, v})||(u, v) e E(G)}. Let κ(G) be the connectivity of G. In this paper, we prove that the pessimistic diagnosability of G, denoted by t_p(G), is equal to n_0 if the following two conditions hold: (1) for any subset U is contained in V(G) with 2 ≤ |U| ≤ 2(n_0 - κ(G)), |N_G(U)| ≥ n_0; (2) |V(G)| ≥ 2n_0 + κ(G). As examples of its applications, we prove that the pessimistic diagnosabili-ties of n-dimensional hypercube-like network XQ_n, dual-cube DC_n, pancake network P_n, and burnt pancake graph BP_n are t_p(XQ_n) = 2n - 2 (n ≥ 4), fp(DC_n) = 2n (n≥ 4), t_p(P_n) = 2n - 4 (n ≥ 4) and t_p(BP_n) = 2n - 2 (n ≥ 3), respectively.
收起
摘要 :
The (s+ t + 1)-dimensional exchanged crossed cube ECQ(s,t) combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ(s, t) has more attractive properties than other variations of the b...
展开
The (s+ t + 1)-dimensional exchanged crossed cube ECQ(s,t) combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ(s, t) has more attractive properties than other variations of the basic hypercube in terms of the smaller diameter, fewer edges, and lower cost factor. In this paper, we study the diagnosability of ECQ(s, t) under the pessimistic diagnosis strategy based on two diagnostic models: the PMC model and the MM* model. And we obtain the following results: if 1 ≤ s ≤ t, the diagnosability of the ECQ(s, t) are both 2s underthe pessimistic diagnosis strategy based on the two models.
收起
原文获取